package calculation;

/**
 * 爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
 *
 * 爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。
 *
 * 当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？
 *
 * @author 78044
 */
public class Topic2 {

    public static double new21Game(int n, int k, int w) {

        if (k == 0) {
            return 1.0;
        }
        // 最大能取到的数为 K-1+w  所以应该取 N 与 K-1+W的最小值 N>K-1 所以为了减少判断，取N+w
        double[] db = new double[n + w];
        // 第一次取到的数为 i ,若i>=K 且i<= min(N,K-1+w)时，游戏结束
        for (int i = k; i <= n && i <= k + w - 1; i++) {
            db[i] = 1.0;
        }
        //        for(int i = K-1;i>=0;i--){
//            for (int j = 1 ; j <= w; j++) {
//                db[i] += db[i+j]/w;
//            }
//        }
        db[k - 1] = 1.0 * Math.min(n - k + 1, w) / w;
        for (int i = k-2; i >= 0; i--) {
            db[i] = db[i + 1] - (db[i + w + 1] - db[i + 1]) / w;
        }
        return db[0];
    }

    public static double new21Game2(int n, int k, int w) {
        if (k == 0) {
            return 1.0;
        }
        double[] dp = new double[k + w];
        for (int i = k; i <= n && i < k + w; i++) {
            dp[i] = 1.0;
        }
        for (int i = k - 1; i >= 0; i--) {
            for (int j = 1; j <= w; j++) {
                dp[i] += dp[i + j] / w;
            }
        }
        return dp[0];
    }



    public static void main(String[] args) {
        System.out.println(new21Game(21,17,10));
        System.out.println(new21Game2(21,17,10));
    }
}
